#pragma once

#include "stack"
#include "deque"
#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。


示例 1 ：

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2 ：

输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 ：

输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 *
 * */

///todo 网上都是单调站 写其实说白了还算一个思想 思路，从左到右，找第一个比后面大的字符，删除，清零，k次扫描。
///我是不太明白他们为啥要搞一个单调站
string removeKdigits(string num, int k) {

    int count = 0;
    deque<char> s;
    for (int i = 0; i < num.size(); ++i) {
        if (s.empty()) {
            s.push_back(num[i]);
        } else {

            //1432219 因为每次去除从高到低位的 高位比低位大的数
            char pre = s.back();
            if (pre <= num[i]) {
                s.push_back(num[i]);
            } else if (count <= k) {
                while (!s.empty() && count < k && pre > num[i]) {
                    s.pop_back();
                    count++;
                    if (s.empty()) break;
                    pre = s.back();

                }
                s.push_back(num[i]);
            }
        }

    }

    while (!s.empty() && count < k) {
        s.pop_front();
        ++count;
    }

    std::string sww(s.begin(), s.end());

    while (!sww.empty() && sww[0] == '0')
        sww.erase(sww.begin());

    if (s.size() == 0)
        return "0";

    return sww;//string(s.begin(), s.end());
}